import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.Map;

public class LRUCache1 {
    class Node {
        public int key;
        public int value;
        public Node pre;
        public Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    Map<Integer, Node> map = new HashMap();
    //链表头
    Node head = null;
    //链表尾
    Node tail = null;
    //容量
    int capacity;

    public LRUCache1(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.pre = head;

    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        put(node.key, node.value);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            //移除该节点
            Node cur = map.get(key);
            removeNode(cur);
        } else {
            if (capacity == map.size()) {
                Node cur = head.next;
                removeNode(cur);
            }
        }
        //放到结尾
        Node tmp = new Node(key, value);
        addTail(tmp);
    }

    private void removeNode(Node cur) {
        map.remove(cur.key);
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
        cur.pre = null;
        cur.next = null;
    }

    private void addTail(Node cur) {
        tail.pre.next = cur;
        cur.next = tail;
        cur.pre = tail.pre;
        tail.pre = cur;
        map.put(cur.key,cur);
    }

    public static void main(String[] args) {
        LRUCache1 cache = new LRUCache1(2 /* 缓存容量 */);

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        System.out.println(cache.get(2));
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}
